import java.awt.print.Book;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;
import javax.xml.stream.XMLOutputFactory;
import javax.xml.stream.XMLStreamWriter;

import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.NamedNodeMap;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
import org.w3c.dom.UserDataHandler;







public class SentenceParser {
	final String WORD = "word";
	final String TEXT_ATTR = "text";
	final String INDEX_ATTR = "index";
	final String SENTENSE = "sentense";
	final String ROOT = "sentenses";
	
	private class Pair implements Comparable<Pair> {
		private String master;
		private String slave;
		private int indexMaster;
		private int indexSlave;
		private int number;
		public Pair(String master, String slave, int indexMaster, int indexSlave, int number) {
			this.master = master;
			this.slave = slave;
			this.indexMaster = indexMaster;
			this.indexSlave = indexSlave;
			this.number = number;
		}
		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			if (o.number < number) {
				return -1;
			} 
			if (o.number > number) {
				return 1;
			}
			return 0;
		}
		
	
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "(" +  master + ", " + slave + ", " + number + ")"; 
		}
		
		
	}
	
	private class PairTree {
		private Collection<PairTree> childs = new ArrayList<PairTree>();
		private int rootIndex = -1;
		public PairTree(int root) {
			this.rootIndex = root;
		}
		public void addChild(int child) {
			childs.add(new PairTree(child));
		}
		public void addChilds(Collection<PairTree> in) {
			
			childs.addAll(in);
		}
		public PairTree[] getChilds() {
			PairTree[] arr = new PairTree[childs.size()];
			
			return childs.toArray(arr);
		}
		@Override
		public boolean equals(Object obj) {
			// TODO Auto-generated method stub
			if (obj instanceof PairTree) {
				PairTree o = (PairTree)obj;
				return o.rootIndex == rootIndex;
			}
			return super.equals(obj);
		}
		
		
	}
	private String sentence;
	private Dictionary dict;
	private String[] splitSentence;
	
	private List<Pair> resultPairs = new ArrayList<SentenceParser.Pair>();
	
	public SentenceParser (String sentence, Dictionary dict) {
		this.sentence = sentence;
		splitSentence = sentence.split("[\\p{Space}\\p{Punct}]+");
		List<Dictionary.DictElement> elements = new ArrayList<Dictionary.DictElement>();
		final Set<Pair> pairs = new TreeSet<Pair>();
		Dictionary.DictElement addEl;
		for (String word : splitSentence) {
			if (word.trim().length() > 0 ) {
				word = Util.getStem(word);
				
				if ((addEl = dict.getElementByMaster(word)) != null) {
					elements.add(addEl);
				}
			}
		}

		boolean [][] matrix = new boolean[elements.size()][elements.size()];
		for (boolean[] row : matrix) {
			Arrays.fill(row, true);
			
		}		
		for (int i = 0 ; i < matrix.length; i ++) {
			for (int j = 0; j < matrix[i].length; j++) {
				if (i==j) {
					matrix[i][j] = false;
				}
			}
		}
		

		
		for (int i = 0; i < elements.size(); i++) {
			
			final Dictionary.DictElement currentElement = elements.get(i);
		
			for (int j = 0; j < elements.size(); j ++) {
				if (matrix[i][j] != false) {
					Dictionary.DictElement currentSlave = elements.get(j);
//					if (currentElement.getSlaveCollection().contains(currentSlave.getMaster())) {
						
						Integer slaveNumber = currentElement.getSlaveNumber(currentSlave.getMaster());
						
						if (slaveNumber != 0) {
							pairs.add(new Pair(currentElement.getMaster(),
									           currentSlave.getMaster(), 
									           i, 
									           j, 
									           slaveNumber));
							
						}
//					}
				}
			}
			

			
		}
		Iterator<Dictionary.DictElement> it =  elements.iterator();
		
		for (Pair pair : pairs) {
			if (canMarkPair(pair.indexMaster, pair.indexSlave, matrix)) {
				resultPairs.add(pair);
				matrix = markPair(pair.indexMaster, pair.indexSlave, matrix);
			}
			//Dictionary.Element master = elements.get(i);
			//Collection<Dictionary.Element> slaves = mapElements.get(master);
			
			
		}
		
		
	}
	private boolean canMarkPair(int i , int j , boolean[][] matrix) {
		return matrix[i][j];
	}
	private boolean[][] markPair(int i, int j, boolean[][] matrix) {
		matrix[i][j] = false;
		for (boolean [] row : matrix) {
			row[j] = false;
		}
	
		for (int i_del = j + 1; i_del < matrix.length ; i_del ++) {
			for (int j_del = i + 1; j_del < j; j_del ++ ) {
				matrix[i_del][j_del] = false;
			}
		}
		
		return matrix;
	}
	private boolean[][] unmarkPair(int i, int j,  boolean[][] matrix) {
		return null;
	}
	public String toString() {
		String res  = "";
		for (Pair pair : resultPairs) {
			res += pair.toString() + "\n";
		}
		return res;
	}
	public double getCoverage() {
		Set<Integer> setUnic = new HashSet<Integer>();
		for (Pair p :resultPairs)  {
			setUnic.add(p.indexMaster);
			setUnic.add(p.indexSlave);
		}
		double res =   (double)setUnic.size() / splitSentence.length;
		return res;
	}
	public int getSizeSentense() {
		return splitSentence.length;
	}
	public Element toNodeXml(Document doc) {
		
		List<PairTree> listPairTree = new ArrayList<SentenceParser.PairTree>();
		Set<Integer> added = new HashSet<Integer>();
		for (int i = 0; i < resultPairs.size(); i++ ) {
			
			final Pair pair = resultPairs.get(i);
			if (added.isEmpty() || !added.contains(pair.indexMaster)) {
				PairTree node = new PairTree(pair.indexMaster);
				added.add(pair.indexMaster);
				//Iterator<Pair> it =  resultPairs.iterator();
				if (isChildRoot(resultPairs, pair.indexMaster)) {
					node.addChilds(findChilds(added, resultPairs, pair.indexMaster));
					listPairTree.add(node);
					
					
				} 
				
					
				
			}
			
		}
		Element root = null;
		
			//Document doc = DocumentBuilderFactory.newInstance().newDocumentBuilder().newDocument();
			root = doc.createElement(SENTENSE);
			root.setAttribute(TEXT_ATTR, sentence );
			doc.appendChild(root);
			for (PairTree pairNode : listPairTree) {
				
				Element el  = doc.createElement(WORD);
				el.setAttribute(TEXT_ATTR, splitSentence[pairNode.rootIndex]);
				el.setAttribute(INDEX_ATTR, String.valueOf(pairNode.rootIndex));
				for (Element child :getChildsElement(doc, pairNode)) {
					el.appendChild(child);
				}
				root.appendChild(el);
			}
			for (int i = 0; i < splitSentence.length; i++) {
				if (!added.contains(i)) {
					Element el  = doc.createElement(WORD);
					el.setAttribute(TEXT_ATTR, splitSentence[i]);
					el.setAttribute(INDEX_ATTR, String.valueOf(i));
					root.appendChild(el);
				}
			}
			
		
	
	
		return root;
	}
	private Collection<Element> getChildsElement(Document doc, PairTree pairNode) {
		Collection<Element> retCol = new ArrayList<Element>();
		for (PairTree pairChild :pairNode.getChilds()) {
			Element el  = doc.createElement(WORD);
			el.setAttribute(TEXT_ATTR, splitSentence[pairChild.rootIndex]);
			el.setAttribute(INDEX_ATTR, String.valueOf(pairChild.rootIndex));
			for (Element child :getChildsElement(doc, pairChild)) {
				el.appendChild(child);
			}
			retCol.add(el);
			
		}
		return retCol;
	}
	private boolean isChildRoot(Collection<Pair> pairs, int indexRoot) {
		for (Pair pair : pairs) {
			if (pair.indexSlave == indexRoot) {
				return false;
			}
		} 
		return true;
		
	}
	public Collection<PairTree> findChilds(Collection<Integer> added, Collection<Pair> pairs, int masterIndex) {
		Collection<PairTree> coll = new ArrayList<SentenceParser.PairTree>();
		
		for (Pair p : pairs) {
			if (p.indexMaster == masterIndex) {
				PairTree el =  new PairTree(p.indexSlave);
				el.addChilds(findChilds(added, pairs, p.indexSlave));
				added.add(p.indexSlave);
				coll.add(el);
				
			}
			
 		}
		return coll;
	}
	
}
